class Solution {
    public:
        int minFallingPathSum(vector<vector<int>>& matrix) {
            int n = matrix.size();
            int m = matrix[0].size();
            vector<vector<int>> dp(n,vector<int>(m,0));
            for(int i = 0 ; i < m ; i++)    dp[0][i] =matrix[0][i];
    
            for(int i = 1 ; i < n ; i ++){
                for(int j = 0 ; j < m ; j++){
                    if( j == m-1 )
                        dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + matrix[i][j];
                    else if( j == 0 )
                        dp[i][j] = min(dp[i-1][j],dp[i-1][j+1]) + matrix[i][j];
                    else 
                        dp[i][j] = min({dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]}) + matrix[i][j];
                }
            }
            int ret = INT_MAX;
            for(int j = 0 ; j < m;j++){
                ret = dp[n-1][j] < ret? dp[n-1][j] : ret;
            }
            return ret;
        }
    };